﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FrogEngine
{
	public interface IBinarySearchTree<K, T, N> : ITree<N>
	{
		N Find(N start, K key);
		void InsertItem(K key, T value);
		void RemoveItem(K key);
		void InOrderTraversal<Y>(N start, Action<Y> visitedAction);
	}

	public interface IBinaryTreeNode<K, T> : ITreeNode<K, T>
	{
		IBinaryTreeNode<K, T> Parent { get; set; }
		IBinaryTreeNode<K, T> Left { get; set; }
		IBinaryTreeNode<K, T> Right { get; set; }
	}

	public class BinarySearchTree<K, T> : BinaryTreeCommon<K, T>, IBinarySearchTree<K, T, IBinaryTreeNode<K, T>>
		where K : IComparable
	{
		public BinarySearchTree()
		{
		}

		public BinarySearchTree(IBinaryTreeNode<K, T> root)
		{
			Root = root;
			Root.Parent = null;
		}

		protected override IBinaryTreeNode<K, T> CreateNode(IBinaryTreeNode<K, T> parent, K key, T item)
		{
			return new BinaryTreeNode<K, T>(parent, key, item);
		}
	}

	public class BinaryTreeNode<K, T> : ITreeNode<K, T>, IBinaryTreeNode<K, T>
	{
		public BinaryTreeNode()
		{
		}

		public BinaryTreeNode(IBinaryTreeNode<K, T> parent)
		{
			this.parent = parent;
		}

		public BinaryTreeNode(IBinaryTreeNode<K, T> parent, K key, T value)
		{
			this.parent = parent;
			this.key = key;
			this.val = value;
		}

		public BinaryTreeNode(IBinaryTreeNode<K, T> parent, K key, T value, IBinaryTreeNode<K, T> left, IBinaryTreeNode<K, T> right)
		{
			this.parent = parent;
			this.key = key;
			this.val = value;
			this.left = left;
			this.right = right;
		}

		private IBinaryTreeNode<K, T> parent;
		public IBinaryTreeNode<K, T> Parent
		{
			get { return parent; }
			set { parent = value; }
		}

		private IBinaryTreeNode<K, T> left;
		public IBinaryTreeNode<K, T> Left
		{
			get { return left; }
			set { left = value; }
		}

		private IBinaryTreeNode<K, T> right;
		public IBinaryTreeNode<K, T> Right
		{
			get { return right; }
			set { right = value; }
		}

		private K key;
		public K Key
		{
			get { return key; }
			set { key = value; }
		}

		private T val;
		public T Value
		{
			get { return val; }
			set { val = value; }
		}

		public bool IsExternal
		{
			get { return left == null && right == null; }
		}

		private bool visited;
		public bool Visited
		{
			get { return visited; }
			set { visited = value; }
		}
	}

	public abstract class BinaryTreeCommon<K, T> : ITree<IBinaryTreeNode<K, T>>
		where K : IComparable
	{
		protected abstract IBinaryTreeNode<K, T> CreateNode(IBinaryTreeNode<K, T> parent, K key, T item);

		private IBinaryTreeNode<K, T> root;
		public IBinaryTreeNode<K, T> Root
		{
			get { return root; }
			set { root = value; }
		}

		public virtual void InsertItem(K key, T item)
		{
			if (Root == null)
			{
				Root = CreateNode(null, key, item);
				Root.Left.Parent = Root;
				Root.Right.Parent = Root;
				return;
			}

			var node = Find(Root, key);
			if (node.IsExternal)
			{
				node.Key = key;
				node.Value = item;
				node.Left = CreateNode(node, default(K), default(T));
				node.Right = CreateNode(node, default(K), default(T));
			}
			else
			{
				node.Key = key;
				node.Value = item;
			}
		}

		public virtual IBinaryTreeNode<K, T> Find(IBinaryTreeNode<K, T> start, K key)
		{
			if (start.IsExternal)
				return start;
			int compareVal = key.CompareTo(start.Key);
			if (compareVal < 0)
				return Find(start.Left, key);
			else if (compareVal > 0)
				return Find(start.Right, key);
			else
				return start;
		}

		public virtual void RemoveItem(K key)
		{
			var node = Find(Root, key);
			if (node.Value == null)
				return;

			Remover(node);
		}

		private void Remover(IBinaryTreeNode<K, T> node)
		{
			if (node.Left.IsExternal && node.Right.IsExternal)
			{
				var parent = node.Parent;
				if (parent.Left == node)
					parent.Left = new BinaryTreeNode<K, T>(parent);
				else if (parent.Right == node)
					parent.Right = new BinaryTreeNode<K, T>(parent);
				node = null;
			}
			else if (node.Left.IsExternal)
			{
				var parent = node.Parent;
				var newChild = node.Right;
				if (node == parent.Left)
				{
					parent.Left = newChild;
				}
				else
				{
					parent.Right = newChild;
				}
				newChild.Parent = parent;
				node = null;
			}
			else if (node.Right.IsExternal)
			{
				var parent = node.Parent;
				var newChild = node.Left;
				if (node == parent.Left)
				{
					parent.Left = newChild;
				}
				else
				{
					parent.Right = newChild;
				}
				newChild.Parent = parent;
				node = null;
			}
			else
			{
				var rightSub = node.Right;
				IBinaryTreeNode<K, T> min = rightSub;
				while (!min.Left.IsExternal)
					min = min.Left;
				node.Key = min.Key;
				node.Value = min.Value;
				Remover(min);
			}
		}

		public virtual int Size
		{
			get
			{
				int count = 0;
				InOrderTraversal(root, new Action<IBinaryTreeNode<K, T>>(delegate { count++; }));
				return count;
			}
		}

		public int Height()
		{
			return Height(root);
		}

		public int Height(IBinaryTreeNode<K, T> start)
		{
			if (start.IsExternal)
				return 0;
			else
			{
				int maxHeight = 0;
				maxHeight = Math.Max(maxHeight, Height(start.Left));
				maxHeight = Math.Max(maxHeight, Height(start.Right));
				return maxHeight + 1;
			}
		}

		public int Depth(IBinaryTreeNode<K, T> node)
		{
			int count = 0;
			var currentNode = node;
			while (currentNode != root)
			{
				currentNode = currentNode.Parent;
				count++;
			}
			return count;
		}

		public void PreOrderTraversal<Y>(IBinaryTreeNode<K, T> start, Action<Y> visitAction)
		{
			if (start == null)
				return;

			visitAction((Y)start);
			PreOrderTraversal<Y>(start.Left, visitAction);
			PreOrderTraversal<Y>(start.Right, visitAction);
		}

		public void PostOrderTraversal<Y>(IBinaryTreeNode<K, T> start, Action<Y> visitAction)
		{
			if (start == null)
				return;

			PostOrderTraversal<Y>(start.Left, visitAction);
			PostOrderTraversal<Y>(start.Right, visitAction);
			visitAction((Y)start);
		}

		public void InOrderTraversal<Y>(IBinaryTreeNode<K, T> start, Action<Y> visitedAction)
		{
			if (start == null)
				return;

			InOrderTraversal(start.Left, visitedAction);
			visitedAction((Y)start);
			InOrderTraversal(start.Right, visitedAction);
		}
	}
}
